﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
http://www.spoj.pl/problems/PALIN/
 * A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133
Output:
818
2222
*/
namespace CSharpAlgorithm
{
    class NextPalindrome
    {
        public NextPalindrome()
        {
            int testCase = Int32.Parse(Console.ReadLine());
            while (testCase-- > 0)
            {
                char[] input = Console.ReadLine().Trim().ToCharArray();
                int left, right, center1, center2;
                if (input.Length % 2 == 0)
                {
                    left = input.Length / 2 - 1;
                    right = left + 1;
                    center1 = left;
                    center2 = right;
                }
                else
                {
                    left = input.Length / 2 - 1;
                    right = left + 2;
                    center1 = left + 1;
                    center2 = center1;
                }
                bool rightUp = false;
                while (left >= 0)
                {
                    if (rightUp)
                    {
                        input[right] = input[left];
                        left--;
                        right++;
                        continue;
                    }
                    if (input[left] > input[right])
                    {
                        input[right] = input[left];
                        rightUp = true;
                    }
                    else if(input[left] < input[right])
                    {
                        CenterUp(ref input, ref center1, ref center2);
                        left = center1;
                        right = center2;
                        rightUp = true;
                    }
                    left--;
                    right++;
                }
                Console.WriteLine(input);
            }
        }
        private void CenterUp(ref char[]input, ref int center1, ref int center2)
        {

            while (input[center1] == '9')
            {
                input[center1] = '0';
                input[center2] = '0';
                center1--;
                center2++;
            }
            input[center1]++;
            if (center1 != center2)
            {
                input[center2] = input[center1];
            }
        }
    }
}
